package c_heap.a_max_heap;

/**
 * @Author: DeLucia
 * @Description:
 * @Date: 2019/1/26 23:26.
 * <p>
 * 最大二叉堆
 * <p>
 * 堆是一钟树结构的优先队列
 * 优先队列 常用于处理动态数据
 * 实现方式     入队      出队
 * 1.普通数组   o(1)     o(N)
 * 2.顺序数组   o(n)     o(1)
 * 3.堆        o(logn)  o(logn)
 * <p>
 * 可见处理的数据如果是需要频繁入队和出队的动态变化的话
 * 使用堆是一种很好的选择
 * <p>
 * 另外堆可以用nlog(m)解决"找出数组中从小到大前m个元素"这样的问题
 * 快于使用nlogn的排序算法
 * <p>
 * 最大堆需要满足的性质:(根节点是最大值)
 * 1. 堆中某个节点的值总是不大于其父节点的值(最大堆)
 * 2. 堆总是一颗完全二叉树.(除了最下层都必须满叶子节点, 最下层叶子节点可以不满,但必须都是靠左边排列)
 * <p>
 * (同样也可以推导出最小堆的响应性质..)
 * <p>
 * 堆的树结构也可以用数组模拟实现 从上层到下层按照从左到右设置索引
 * 一种经典的实现是从1开始保存对应索引的元素, 0位置留空, 根据索引i计算父节点以及左右叶子节点的公式可以推导出
 * parent(i) = i/2 (取整)
 * leftChild(i) = 2*i
 * rightChild(i) = 2*i+1
 * <p>
 * 优化：
 * 1. 堆中的数组可以根据一定条件自动动态扩容和缩容
 * 2. 交换过程中，可以标记最后的交换位置，一次完成交换过程
 */
@SuppressWarnings("unchecked")
public class MaxBinaryHeap<Item extends Comparable<Item>> {
    private Item[] data;
    private int capacity; // 堆中可容纳元素数量
    private int count; // 堆中元素数量

    public MaxBinaryHeap(int capacity) {
        this.capacity = capacity;
        count = 0;
        data = (Item[]) new Comparable[capacity + 1];
    }

    public MaxBinaryHeap(Item[] arr) {
        capacity = arr.length;
        data = (Item[]) new Comparable[capacity + 1];
        
        for (int i = 0; i < capacity; i++) {
            data[i + 1] = arr[i];
        }
        count = capacity;
        for (int i = count/2; i >= 1; i--) {
            shiftDown(i);
        }
    }

    public int size() {
        return count;
    }

    public boolean isEmpty() {
        return count == 0;
    }

    /**
     * 插入一个新元素
     * 返回新的最大堆的元素数
     *
     * @param item
     * @return
     */
    public int unshift(Item item) {
        assert count <= capacity - 1;
        data[++count] = item;
        shiftUp(count); // 向上交换 - 维护最大堆的性质
        // System.out.println(Arrays.toString(data)); // test
        return count;
    }

    /**
     * 最大堆中插入元素后
     * 需要逐级和父元素比较
     * 如果比父元素还大就向上进行shiftUp(向上交换)操作
     *
     * @param k 新插入元素在data中的索引
     *          新插入元素如果比父节点大就和父节点交换位置 - 维护最大堆的性质
     *          即堆中某个节点的值总是不大于其父节点的值
     */
    private void shiftUp(int k) {
        // k=1时 只有一个根元素 不存在和父元素交换
        // 只有当k>1时且k的元素比父元素k/2还大的时候才需要交换
        while (k > 1 && data[k / 2].compareTo(data[k]) < 0) {
            swap(k, k / 2);
            k /= 2; // 继续向父元素进行迭代
        }
    }

    /**
     * 删除并同时返回堆顶的最大元素
     *
     * @return 堆顶元素
     * 1. 将堆顶元素和队尾元素交换
     * 2. 从堆顶元素开始进行向下交换 - 维持最大堆性质
     */
    public Item shift() {
        assert count > 0;
        Item ret = data[1];
        swap(1, count);
        count--;
        shiftDown(1); // 迭代 向下交换 - 维持最大堆性质
        return ret;
    }

    /**
     * 返回堆顶最大元素
     *
     * @return
     */
    public Item getMax() {
        assert count > 0;
        return data[1];
    }

    /**
     * @param k 向下交换的起始下标
     */
    private void shiftDown(int k) {
        while (2 * k <= count) { // 如果k有孩子 - 完全二叉树来说有左孩子就必有右孩子， 所以只需考察是否有左孩子
            int j = 2 * k; // 预设和左孩子交换
            if (j + 1 <= count && data[j + 1].compareTo(data[j]) > 0) {
                j++; // 当右孩子比左孩子大的时候 预设交换元素就改成右孩子
            }
            // 如果操作的元素已经大于或等于它最大的孩子，交换过程结束
            if (data[k].compareTo(data[j]) >= 0) break;
            // 反之 和 其最大孩子进行交换
            swap(k, j);
            // 并继续考察交换后的元素的父元素 -
            k = j;

        }
    }

    private void swap(int m, int n) {
        Item temp = data[m];
        data[m] = data[n];
        data[n] = temp;
    }

    /**
     * 打印测试
     */
    public void printHeapDataTest() {
        if (count == 0) {
            System.out.println("该堆中不包含任何数组");
            return;
        }
        if (size() >= 100) {
            System.out.println("该测试方法只能打印不超过100个容量的堆的树形结构");
            return;
        }
        if (!(data[1] instanceof Integer)) {
            System.out.println("该测试方法只能处理整数数据");
            return;
        }

        System.out.print("HEAP[" + size() + "] : ");
        for (int i = 1; i <= size(); i++) {
            System.out.print(data[i] + " ");
        }
        System.out.print("\n");
    }

    /**
     * 打印测试
     * 依次出队， 从大到小打印
     */
    public void printHeapDescSortedTest() {
        int len = size();
        System.out.print("HEAP[" + len + "] : ");
        for (int i = 0; i < len; i++) {
            Item item = shift();
            System.out.print(item + " ");
        }
        System.out.print(" <-- sorted desc \n");
    }

    /**
     * 打印测试
     * 传入原数组， 返回从小到大排序好的数组
     * 同时打印测试输出
     */
    public Comparable[] printHeapAscSortedTest() {
        int len = size();
        Comparable[] ret = new Comparable[len];
        for (int i = len - 1; i >= 0; i--) {
            ret[i] = shift();
        }
        System.out.print("HEAP[" + len + "] : ");
        for (int i = 0; i < len; i++) {
            System.out.print(ret[i] + " ");
        }
        System.out.print(" <-- sorted asc \n");

        return ret;
    }

    public static void main(String[] args) {
        MaxBinaryHeap<Integer> maxHeap = new MaxBinaryHeap<>(100);
        for (int i = 0; i < 15; i++) {
            int num = (int) (Math.random() * 100);
            System.out.print(num + " ");
            maxHeap.unshift(num);
        }
        System.out.println();
        maxHeap.printHeapDataTest();
        maxHeap.printHeapDescSortedTest();

        // 对已有数组进行排序的情况
        // 如果一个一个添加到堆中，再一个一个输出，进行排序，效率比较低下
        // 可以通过构造函数对原有数据直接进行heapify处理， 整理成符合堆的结构
        Comparable[] arr = {3, 2, 5, 4, 1, 0,21,52,12,64,2};
        MaxBinaryHeap maxheap2 = new MaxBinaryHeap(arr);
        maxheap2.printHeapDataTest();
        maxheap2.printHeapAscSortedTest();
        // 以上方法还是需要开辟新的空间，如果只是需要单纯排序， 可以直接对原数组进行原地排序
        // 但是无论如何优化 堆排序的虽然是nlogn的时间复杂度， 效率上都不如归并排序以及快速排序
        // 堆的优势在于处理动态数据（需要频繁入队出队）时效率更好！！

    }
}


